package com.leetcode.no19;


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast, slow;
        fast = slow = head;

        // fast先走n步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        if(fast == null){
            return head.next;
        }

        // 快慢指针同步向前
        while ( fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        //  此时slow在倒数第n+1个的位置上
        // 把倒数第n个节点删除
        slow.next = slow.next.next;
        return head;
    }
}
